<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <div>
            <!-- 输入：l1 = [1,2,4], l2 = [1,3,4]
          输出：[1,1,2,3,4,4]
          示例 2：
          
          输入：l1 = [], l2 = []
          输出：[]
          示例 3：
          
          输入：l1 = [], l2 = [0]
          输出：[0]
          
          来源：力扣（LeetCode）
          链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
          著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 -->
        </div>
        <script>
            /**
             * Definition for singly-linked list.
             * function ListNode(val) {
             *     this.val = val;
             *     this.next = null;
             * }
             */
            /**
             * @param {ListNode} l1
             * @param {ListNode} l2
             * @return {ListNode}
             */
            let link1 = {
                val: 1,
                next: {
                    val: 4,
                    next: {
                        val: 6,
                        next: null,
                    },
                },
            };
            let link2 = {
                val: 2,
                next: {
                    val: 5,
                    next: {
                        val: 7,
                        next: null,
                    },
                },
            };

            // 递归
            var mergeTwoLists1 = function (l1, l2) {
                console.log('mergeTwoLists()------', l1, l2);
                if (l1 === null) {
                    return l2;
                }
                if (l2 === null) {
                    return l1;
                }
                if (l1.val < l2.val) {
                    l1.next = mergeTwoLists(l1.next, l2);
                    console.log('=====>', l1);
                    return l1;
                } else {
                    l2.next = mergeTwoLists(l1, l2.next);
                    console.log('=====>', l2);
                    return l2;
                }
            };

            /**
             * @param {ListNode} l1
             * @param {ListNode} l2
             * @return {ListNode}
             */
            function ListNode(val) {
                this.val = val;
                this.next = null;
            }
            var mergeTwoLists = function (l1, l2) {
                // 虚拟头节点
                let dummy = new ListNode(-1);
                let p = dummy;
                // 两个链表都有值的情况
                while (l1 != null && l2 != null) {
                    // 比较 l1 和 l2 两个指针,将值较小的的节点接到 p 指针
                    if (l1.val < l2.val) {
                        p.next = l1;
                        l1 = l1.next;
                    } else {
                        p.next = l2;
                        l2 = l2.next;
                    }
                    // p 指针不断前进
                    p = p.next;
                }
                p.next = l1 == null ? l2 : l1;
                return dummy.next;
            };

            // 作者：angela-x
            // 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/di-gui-he-fei-di-gui-liang-chong-shi-xia-nfnt/
            // 来源：力扣（LeetCode）
            // 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

            console.log(mergeTwoLists(link1, link2));
        </script>
    </body>
</html>
